CENG 315 Algorithms |
Hw#1 |
Overlapping Rectangles (Due October 18th)
You are given the locations and shapes of several rectangles. Bases of all rectangles lie on the x-axis, so it is possible to represent each rectangle by a triple (Li, Hi, Ri) where Li and Ri denote the left and right x coordinates of the rectangle, respectively, and Hi denotes the rectangle's height. For example,
(1, 3, 5) (2, 7, 4) (7, 8, 9) (10, 4, 12) (3, 5, 8)
is a possible set of rectangles. In a given set of rectangles, some of them may overlap with each other. In the example given above (2, 7, 4) overlaps with (1, 3, 5), (3, 5, 8) overlaps with (2, 7, 4) and (7, 8, 9). (Figure 1)
Figure 1
If overlapping regions of rectangles are removed we obtain the envelope of the given set of rectangles. (Figure 2)
Figure 2
An envelope can be represented by a list of x coordinates and the heights connecting them arranged in order from left to right. The envelope of our example is (1, 3, 2, 7, 4, 5, 7, 8, 9, 0, 10, 4, 12). (The numbers in boldface are the heights.) In this homework you will implement two different algorithms to find the envelope of a given set of rectangles.
The straightforward (incremental) algorithm for this problem is based on adding one rectangle at a time to the envelope. To add a new rectangle to the envelope, scan the envelope from left to right to find where the left side of rectangle fits and then adjust the height of each horizontal line if the height of the rectangle is higher than the existing height until you reach an x coordinate that is greater than the right side of the rectangle. Note that adjusting the height of a horizontal line may require splitting or merging operations. For example inserting (2, 7, 4) to the envelope (1, 3, 5) generates (1, 3, 2, 7, 4, 3, 5) and inserting (2, 8, 5) to (1, 3, 2, 7, 4, 3, 5) generates (1, 3, 2, 8, 5).
The incremental algorithm is clearly correct, but it is not necessarily efficient. In the worst case, to add a new rectangle we may need to scan the whole envelope and compare the height of the rectangle with the heights in the envelope (O(n) comparisons). Hence, the total number of height comparisons will be O(n)+O(n-1)+...+O(1) = O(n^2). To improve the performance of this algorithm we can use divide-and-conquer technique. Instead of extending the solution for n-1 to the solution for n, it is possible to extend a solution for n/2 to a solution for n. First divide the input into two subsets, solve (conquer) each subset recursively, and merge the solutions together. If subsets are of about equal size, and merging operation takes linear time (O(n) height comparisons), the algorithm runs in time O(n log n). It is trivial to divide a set of rectangles into two, but you need to find an algorithm which merges two envelopes into a single envelope.
Regulations
You will submit two files envelope_incremental.c (or cpp) and envelope_divcon.c (or cpp) which implement incremental and divide-and-conquer algorithm described above respectively. Details of submission will be announced later. Input and output specifications for both programs are given below.
Input
Input of your program is a file named envelope.inp. The first line of envelope.inp contains a single integer n (0<n<10000) which denotes the number of rectangles. Each of the following n lines contains three integers Li (0 £ Li < 2000000000), Hi (0 < Hi <1000000) and Ri (Li < Ri <2000000000) representing a rectangle.
envelope.inp
5
1 3 5
2 7 4
7 8 9
10 4 12
3 5 8
Output
Output of your program is a file named envelope.out. The first line of envelope.out must contain the envelope of the set of rectangles given in the input file as a list of integers separated by a blank. In the second line of envelope.out you must print out the total number of height comparisons required to obtain the envelope. Note that this number is not unique and may change depending on the processing order of rectangles. Your programs will be manually checked for correct implementation of algorithms.
envelope.out
1 3 2 7 4 5 7 8 9 0 10 4 12
25